Semiprime

 ( Integer Sequences ) 

In mathematics, a semiprime is a natural number that is the product of exactly two . The two primes in the product may equal each other, so the semiprimes include the Square number of prime numbers. Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Semiprimes are also called biprimes, since they include two primes, or second numbers, by analogy with how "prime" means "first". Alternatively non-prime semiprimes are called almost-prime numbers, specifically the "2-almost-prime" biprime and "3-almost-prime" triprime.

---

Examples and variations The semiprimes less than 100 are:

Semiprimes that are not square numbers are called discrete, distinct, or squarefree semiprimes:

The semiprimes are the case $k=2$ of the $k$-, numbers with exactly $k$ prime factors. However some sources use "semiprime" to refer to a larger set of numbers, the numbers with at most two prime factors (including unit (1), primes, and semiprimes).

These are:

---

Formula for number of semiprimes A semiprime counting formula was discovered by E. Noel and G. Panos in 2005. Let $\backslash pi\_2(n)$ denote the number of semiprimes less than or equal to n. Then $$\backslash pi\_2(n)\; =\; \backslash sum\_\{k=1\}^\{\backslash pi\; \backslash left(\backslash sqrt\; n\backslash right)\; \}\; \backslash left\backslash pi\backslash left(\backslash frac\{n\}\{p\_k\}\backslash right)$$ where $\backslash pi(x)$ is the prime-counting function and $p\_k$ denotes the kth prime.

---

Properties Semiprime numbers have no as factors other than themselves. For example, the number 26 is semiprime and its only factors are 1, 2, 13, and 26, of which only 26 is composite.

For a squarefree semiprime $n=pq$ (with $p\backslash ne\; q$) the value of Euler's totient function $\backslash varphi(n)$ (the number of positive integers less than or equal to $n$ that are relatively prime to $n$) takes the simple form $$\backslash varphi(n)=(p-1)(q-1)=n-(p+q)+1.$$ This calculation is an important part of the application of semiprimes in the RSA cryptosystem.

For a square semiprime $n=p^2$, the formula is again simple: $$\backslash varphi(n)=p(p-1)=n-p.$$

---

Applications

]]Semiprimes are highly useful in the area of cryptography and number theory, most notably in public key cryptography, where they are used by RSA and pseudorandom number generators such as Blum Blum Shub. These methods rely on the fact that finding two large primes and multiplying them together (resulting in a semiprime) is computationally simple, whereas finding the original factors appears to be difficult. In the RSA Factoring Challenge, RSA Security offered prizes for the factoring of specific large semiprimes and several prizes were awarded. The original RSA Factoring Challenge was issued in 1991, and was replaced in 2001 by the New RSA Factoring Challenge, which was later withdrawn in 2007.

In 1974 the Arecibo message was sent with a radio signal aimed at a star cluster. It consisted of $1679$ binary digits intended to be interpreted as a $23\; \backslash times\; 73$ bitmap image. The number $1679=23\backslash cdot\; 73$ was chosen because it is a semiprime and therefore can be arranged into a rectangular image in only two distinct ways (23 rows and 73 columns, or 73 rows and 23 columns).

Marcus du Sautoy (2025). 9780230120280, St. Martin's Press. . ISBN 9780230120280

---

See also

• Chen's theorem
• Sphenic number, a product of three distinct primes
• Parity problem (sieve theory)

---

External links

Post Comment